package com.leecode.xiehf.page_03;

import java.util.*;

public class Solution_0105 {
    public static void main(String[] args) {
        Solution_0105 solution = new Solution_0105();
        TreeNode treeNode = solution.buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        System.out.println(treeNode);
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int length = preorder.length;
        if (length == 0) {
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, map, 0, length - 1, 0);
    }

    private TreeNode build(int[] preorder, Map<Integer, Integer> map, int preLeft, int preRight,  int inLeft) {
        if (preLeft > preRight) {return null;}

        // 当前子树根节点
        int preRoot = preLeft;
        // 找到中序的跟节点
        int inRoot = map.get(preorder[preRoot]);

        // 根节点
        TreeNode root = new TreeNode(preorder[preRoot]);
        int sizeLeftSubTree  = inRoot - inLeft;
        root.left = build(preorder, map, preLeft +  1, preLeft + sizeLeftSubTree, inLeft);
        root.right = build(preorder, map, preLeft + sizeLeftSubTree + 1, preRight, inRoot + 1);
        return root;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
